/*
 * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;

import java.io.InvalidObjectException;
import sun.misc.SharedSecrets;

/**
 * 这个类实现了<tt>Set</tt>接口, 由hash表(实际上是<tt>HashMap</tt>实例)支持. 它不保证
 * set的迭代顺序; 特别是, 它不能保证属性随时间保持不变. 此类允许<tt>null</tt>元素.
 *
 * <p>该类为基本操作(<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt>和<tt>size</tt>)
 * 提供了恒定的时间性能, 假设hash函数将元素适当地分散到桶中. 迭代这个set所需的时间与<tt>HashSet</tt>
 * 实例的大小(元素的数量)加上支持HashMap实例的"容量"(桶数)之和成正比. 因此, 如果迭代性能很重要,
 * 那么不要将初始容量设置得太高(或负载因子设置得太低)是非常重要的.
 *
 * <p><strong>请注意, 此实现不同步.</strong> 如果多个线程同时访问一个hash set, 并且
 * 至少有一个线程修改了这个hash set, 那么它<i>必须</i>从外部同步. 这通常是在自然封装set
 * 的某些对象上同步来实现的.
 *
 * 如果不存在这样的对象, 则应该使用
 * {@link Collections#synchronizedSet Collections.synchronizedSet}方法对集合
 * 进行"包装". 这最好咋其创建时完成, 以防止意外的不同步访问set:<pre>
 *   Set s = Collections.synchronizedSet(new HashSet(...));</pre>
 *
 * <p>这个类的<tt>iterator</tt>方法返回的iterator是<i>fail-fast</i>: 如果在iterator
 * 创建后的任何时间, 除了通过iterator自己的<tt>iterator</tt>方法以外的任何方式修改set,
 * iterator将抛出{@link ConcurrentModificationException}. 因此, 在面对并发修改时,
 * iterator会快速而干净地失败, 而不是在未来不确定的时间发生任意的、不确定的行为.
 *
 * <p>注意, iterator的快速失败行为不能得到保障, 因为一般来说, 在存在不同步的并发修改时, 不可能
 * 做出任何硬保证. 快速失败iterator尽可能抛出<tt>ConcurrentModificationException</tt>.
 * 因此, 编写一个依赖于此异常的程序是错误的: <i>iterator的fail-fast行为应该只用于检测错误.</i>
 *
 * <p>这个类是
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework的成员</a>.
 *
 * @param <E> 此set维护的元素的类型
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     Set
 * @see     TreeSet
 * @see     HashMap
 * @since   1.2
 */

public class HashSet<E>
		extends AbstractSet<E>
		implements Set<E>, Cloneable, java.io.Serializable
{
	static final long serialVersionUID = -5024744406713321676L;

	private transient HashMap<E,Object> map;

	// 与支持Map中的对象相关联的虚拟值
	private static final Object PRESENT = new Object();

	/**
	 * 构造一个新的空set; 后台<tt>HashMap</tt>实例具有默认的初始容量
	 * (16)和负载因子(0.75).
	 */
	public HashSet() {
		map = new HashMap<>();
	}

	/**
	 * 构造包含指定set中元素的新set. <tt>HashMap</tt>创建时具有默认负载因子(0.75)
	 * 和足以包含指定set中的元素的初始容量.
	 *
	 * @param c 要将其元素防止草此set中的Collection
	 * @throws NullPointerException 如果指定的collection为null
	 */
	public HashSet(Collection<? extends E> c) {
		map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
		addAll(c);
	}

	/**
	 * 构造一个新的空set; 支持的<tt>HashMap</tt>实例具有指定的初始容量和指定的
	 * 负载因子.
	 *
	 * @param      initialCapacity   hash map的初始容量
	 * @param      loadFactor        hash map的负载因子
	 * @throws     IllegalArgumentException 如果初始容量小于0, 或者负载因子非正
	 */
	public HashSet(int initialCapacity, float loadFactor) {
		map = new HashMap<>(initialCapacity, loadFactor);
	}

	/**
	 * 构造一个新的空set; 支持的<tt>HashMap</tt>实例具有指定初始容量和默认
	 * 负载因子(0.75).
	 *
	 * @param      initialCapacity   hash table的初始容量
	 * @throws     IllegalArgumentException 如果初始容量小于0
	 */
	public HashSet(int initialCapacity) {
		map = new HashMap<>(initialCapacity);
	}

	/**
	 * 构造一个新的空 linked hash set. (这个包私有的构造函数只被LinkedHashSet使用.)
	 * 后台HashMap实例是一个LinkedHashMap, 具有指定的初始容量和指定的负载因子.
	 *
	 * @param      initialCapacity   hash map的初始容量
	 * @param      loadFactor        hash map的负载因子
	 * @param      dummy             忽略(将次构造函数与其他int、float构造函数区分开来.)
	 * @throws     IllegalArgumentException 如果初始容量小于0, 或者负载因子非正
	 */
	HashSet(int initialCapacity, float loadFactor, boolean dummy) {
		map = new LinkedHashMap<>(initialCapacity, loadFactor);
	}

	/**
	 * 返回此set中元素的iterator. 返回的元素没有特定的顺序.
	 *
	 * @return 该set中元素的iterator
	 * @see ConcurrentModificationException
	 */
	public Iterator<E> iterator() {
		return map.keySet().iterator();
	}

	/**
	 * 返回此set中的元素数(其基数).
	 *
	 * @return 该set中的元素数(基数)
	 */
	public int size() {
		return map.size();
	}

	/**
	 * Returns <tt>true</tt> if this set contains no elements.
	 *
	 * @return <tt>true</tt> if this set contains no elements
	 */
	public boolean isEmpty() {
		return map.isEmpty();
	}

	/**
	 * 如果这个set中包含指定的元素, 返回<tt>true</tt>. 更正式地说, 返回
	 * <tt>true</tt>当且仅当这个set中包含一个<tt>e</tt>的元素, 使得
	 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
	 *
	 * @param o 要测试其在此set中的存在性的元素
	 * @return <tt>true</tt>, 如果这个set包含指定的元素
	 */
	public boolean contains(Object o) {
		return map.containsKey(o);
	}

	/**
	 * 如果指定元素不存在, 则将其添加到此set中. 更正式地说, 如果这个set不包含元素
	 * <tt>e2</tt>, 则将指定的元素<tt>e</tt>添加到此set, 从而使
	 * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
	 * 如果这个set已经包含元素, 调用保持该set不变, 并返回<tt>false</tt>.
	 *
	 * @param e 要添加到此set的元素
	 * @return <tt>true</tt>, 如果此set尚未包含指定的元素
	 * element
	 */
	public boolean add(E e) {
		return map.put(e, PRESENT)==null;
	}

	/**
	 * 如果指定元素存在, 则从此set中删除该元素. 更正式地说, 删除一个元素<tt>e</tt>,
	 * 以便<tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
	 * 如果这个set包含这样一个元素. 如果这个set包含元素, 则返回<tt>true</tt>(或者
	 * 等效地, 如果这个集合因调用而发生更改). (一旦调用返回, 这个set将不包含原始).
	 *
	 * @param o 要从此set中删除的对象(如果存在)
	 * @return <tt>true</tt>, 如果此set尚未包含指定的元素
	 */
	public boolean remove(Object o) {
		return map.remove(o)==PRESENT;
	}

	/**
	 * 从该set中删除所有元素.
	 * 此调用返回后, set将为空.
	 */
	public void clear() {
		map.clear();
	}

	/**
	 * Returns a shallow copy of this <tt>HashSet</tt> instance: the elements
	 * themselves are not cloned.
	 *
	 * @return a shallow copy of this set
	 */
	@SuppressWarnings("unchecked")
	public Object clone() {
		try {
			HashSet<E> newSet = (HashSet<E>) super.clone();
			newSet.map = (HashMap<E, Object>) map.clone();
			return newSet;
		} catch (CloneNotSupportedException e) {
			throw new InternalError(e);
		}
	}

	/**
	 * Save the state of this <tt>HashSet</tt> instance to a stream (that is,
	 * serialize it).
	 *
	 * @serialData The capacity of the backing <tt>HashMap</tt> instance
	 *             (int), and its load factor (float) are emitted, followed by
	 *             the size of the set (the number of elements it contains)
	 *             (int), followed by all of its elements (each an Object) in
	 *             no particular order.
	 */
	private void writeObject(java.io.ObjectOutputStream s)
			throws java.io.IOException {
		// Write out any hidden serialization magic
		s.defaultWriteObject();

		// Write out HashMap capacity and load factor
		s.writeInt(map.capacity());
		s.writeFloat(map.loadFactor());

		// Write out size
		s.writeInt(map.size());

		// Write out all elements in the proper order.
		for (E e : map.keySet())
			s.writeObject(e);
	}

	/**
	 * Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
	 * deserialize it).
	 */
	private void readObject(java.io.ObjectInputStream s)
			throws java.io.IOException, ClassNotFoundException {
		// Read in any hidden serialization magic
		s.defaultReadObject();

		// Read capacity and verify non-negative.
		int capacity = s.readInt();
		if (capacity < 0) {
			throw new InvalidObjectException("Illegal capacity: " +
					capacity);
		}

		// Read load factor and verify positive and non NaN.
		float loadFactor = s.readFloat();
		if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
			throw new InvalidObjectException("Illegal load factor: " +
					loadFactor);
		}

		// Read size and verify non-negative.
		int size = s.readInt();
		if (size < 0) {
			throw new InvalidObjectException("Illegal size: " +
					size);
		}
		// Set the capacity according to the size and load factor ensuring that
		// the HashMap is at least 25% full but clamping to maximum capacity.
		capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
				HashMap.MAXIMUM_CAPACITY);

		// Constructing the backing map will lazily create an array when the first element is
		// added, so check it before construction. Call HashMap.tableSizeFor to compute the
		// actual allocation size. Check Map.Entry[].class since it's the nearest public type to
		// what is actually created.

		SharedSecrets.getJavaOISAccess()
				.checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));

		// Create backing HashMap
		map = (((HashSet<?>)this) instanceof LinkedHashSet ?
				new LinkedHashMap<E,Object>(capacity, loadFactor) :
				new HashMap<E,Object>(capacity, loadFactor));

		// Read in all elements in the proper order.
		for (int i=0; i<size; i++) {
			@SuppressWarnings("unchecked")
			E e = (E) s.readObject();
			map.put(e, PRESENT);
		}
	}

	/**
	 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
	 * and <em>fail-fast</em> {@link Spliterator} over the elements in this
	 * set.
	 *
	 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
	 * {@link Spliterator#DISTINCT}.  Overriding implementations should document
	 * the reporting of additional characteristic values.
	 *
	 * @return a {@code Spliterator} over the elements in this set
	 * @since 1.8
	 */
	public Spliterator<E> spliterator() {
		return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
	}
}
